Minimax 和 Alpha

您所在的位置：网站首页 › tic tac toe游戏规则英语 › Minimax 和 Alpha

Minimax 和 Alpha

2024-07-09 22:04| 来源: 网络整理| 查看: 265

Minimax 和 Alpha-beta 剪枝算法简介，及以此实现的井字棋游戏（Tic-tac-toe）发表于 2018-03-04 更新于 2021-12-21 阅读次数：

前段时间用 React 写了个2048 游戏来练练手，准备用来回顾下 React 相关的各种技术，以及试验一下新技术。在写这个2048的过程中，我考虑是否可以在其中加入一个 AI 算法来自动进行游戏，于是我找到了这篇文章：2048-AI程序算法分析，文中介绍了 minimax 算法和 alpha-beta 剪枝算法。于是我决定先学习下这两种算法，并以此写了这个 tic-tac-toe 游戏：tic-tac-toe-js（代码见此处）。本文将说明如何用 JavaScript 来简单地实现算法，并将其运用到 tic-tac-toe 游戏中。

Minimax 算法简介

我觉得要解释 minimax 算法的原理，需要用示意图来解释更清晰，以下的几篇文章都对原理说的足够清楚。

2048-AI程序算法分析 Tic Tac Toe: Understanding the Minimax Algorithm An Exhaustive Explanation of Minimax, a Staple AI Algorithm

其中后面的两篇文章都是以 tic-tac-toe 游戏为例，并用 Ruby 实现。

以棋类游戏为例来说明 minimax 算法，每一个棋盘的状态都会对应一个分数。双方将会轮流下棋。轮到我方下子时，我会选择分数最高的状态；而对方会选择对我最不利的状态。可以这么认为，每次我都需要从对手给我选择的最差（min）局面中选出最好（max）的一个，这就是这个算法名称 minimax 的意义。

（图片来自于 http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html）

我们接下来会解决这样一个问题，如上图所示，正方形的节点对应于我的决策，圆形的节点是对手的决策。双方轮流选择一个分支，我的目标是让最后选出的数字尽可能大，对方的目标是让这个数字尽可能小。

Minimax 算法的实现

为了简单起见，对于这个特定的问题，我用了一个嵌套的数组来表示状态树。

123456789101112131415161718const dataTree = [ [ [ [3, 17], [2, 12] ], [ [15], [25, 0] ] ], [ [ [2, 5], [3] ], [ [2, 14] ] ]];

图中的节点分为两种类型：

Max 节点：图中的正方形节点，对应于我的回合，它会选取所有子节点中的最大值作为自身的值 Min 节点：图中的圆形节点，对应于对手的回合，它会选取所有子节点中的最小值作为自身的值

先定义一个 Node 类，constructor 如下：

12345constructor(data, type, depth) { this.data = data; this.type = type; // 区分此节点的种类是 max 或 min this.depth = depth;}

根节点的 depth 为0，以下的每一层 depth 依次加一。最底层的节点 depth 为4，其 data 是写在图中的数字，其它层节点的 data 均是一个数组。

接下来考虑如何给每个节点打分，可能会出现这样的几种情况：

最底层的节点，直接返回本身的数字中间层的 max 节点，返回子节点中的最大分数中间层的 min 节点，返回子节点中的最小分数

为方便描述，我们按照由上到下、由左到右的顺序给图中节点进行标号。节点1是 max 节点，从节点2和节点3中选择较大值；而对于节点2来说，需要从节点4，5中选取较小值。很显然，我们这里要用递归的方法来实现，当搜索到最底层的节点时，递归过程开始返回。

minimax tree mark

以下是打分函数 score 的具体代码：

123456789101112131415161718192021222324252627282930score() { // 到达了最大深度后，此时的 data 是数组最内层的数字 if (this.depth >= 4) { return this.data; } // 对于 max 节点，返回的是子节点中的最大值 if (this.type === 'max') { let maxScore = -1000; for (let i = 0; i < this.data.length; i++) { const d = this.data[i]; // 生成新的节点，子节点的 type 会和父节点不同 const childNode = new Node(d, changeType(this.type), this.depth + 1); // 递归获取其分数 const childScore = childNode.score(); if (childScore > maxScore) { maxScore = childScore; } } return maxScore; } // 对于 min 节点，返回的是子节点中的最小值 else if (this.type === 'min') { // 与上方代码相似，省略部分代码 }}

完整的 minimax 算法代码

Alpha-beta 剪枝算法简介

Alpha-beta 剪枝算法可以认为是 minimax 算法的一种改进，在实际的问题中，需要搜索的状态数量将会非常庞大，利用 alpha-beta 剪枝算法可以去除一些不必要的搜索。

关于 alpha-beta 算法的具体解释可以看这篇文章 Minimax with Alpha Beta Pruning。我们在前文中考虑的那张图就来自这篇文章，之后我们会用 alpha-beta 剪枝算法来改进之前的解决方案。

剪枝算法中主要有这么些概念：

每一个节点都会由 alpha 和 beta 两个值来确定一个范围 [alpha, beta]，alpha 值代表的是下界，beta 代表的是上界。每搜索一个子节点，都会按规则对范围进行修正。

Max 节点可以修改 alpha 值，min 节点修改 beta 值。

如果出现了 beta maxScore) { maxScore = childScore; // 相对于 minimax 算法，alpha-beta 剪枝算法在这里增加了一个更新 alpha 值的操作 this.alpha = maxScore; } // 如果满足了退出的条件，我们不需要继续搜索更多的节点了，退出循环 if (this.alpha >= this.beta) { break; }

相对应的是在 min 节点中，我们更新的将是 beta 值。好了，只需要做这么些简单的改变，就将 minimax 算法改变成了 alpha-beta 剪枝算法了。

最后看看如何将算法应用到 tic-tac-toe 游戏中。

完整的 alpha-beta 剪枝算法代码

Tic-tac-toe 游戏中的应用

Tic-tac-toe，即井字棋游戏，规则是在双方轮流在 3x3 的棋盘上的任意位置下子，率先将三子连成一线的一方获胜。

这就是一个非常适合用 minimax 来解决的问题，即使在不考虑对称的情况，所有的游戏状态也只有 9! = 362880 种，相比于其它棋类游戏天文数字般的状态数量已经很少了，因而很适合作为算法的示例。

我在代码中将棋盘的状态用一个长度为9的数组来表示，然后利用 canvas 绘制出一个简易的棋盘，下子的过程就是修改数组的对应位置然后重绘画面。

现在我们已经有了现成的 minimax 和 alpha-beta 剪枝算法，只要加上一点儿细节就能完成这个游戏了😀。

先来定义一个 GameState 类，其中保存了游戏的状态，对应于之前分析过程中的节点，其 constructor 如下：

1234567891011constructor(board, player, depth, alpha, beta) { this.board = board; // player 是用字符 X 和 O 来标记当前由谁下子，以此来判断当前是 max 还是 min 节点 this.playerTurn = player; this.depth = depth; // 保存分数最高或最低的状态，用于确定下一步的棋盘状态 this.choosenState = null; this.alpha = alpha || -Infinity; this.beta = beta || Infinity;}

为进行游戏，首先需要一个 checkFinish 函数，检查游戏是否结束，结束时返回胜利者信息。搜索的过程是在 getScore 函数中完成的，每次搜索先检查游戏是否结束，平局返回零分，我们的算法是站在 AI 的角度来考虑的，因此 AI 胜利时返回10分，AI 失利时返回-10分。

12345678// alphabeta.js 中的 getScore() 方法const winner = this.checkFinish();if (winner) { if (winner === 'draw') return 0; if (winner === aiToken) return 10; return -10;}

接着是对 max 和 min 节点的分类处理：

1234567891011121314151617181920212223242526272829303132333435363738// alphabeta.js 中的 getScore() 方法// 获得所有可能的位置，利用 shuffle 加入随机性const availablePos = _.shuffle(this.getAvailablePos());// 对于 max 节点，返回的是子节点中的最大值if (this.playerTurn === aiToken) { let maxScore = -1000; let maxIndex = 0; for (let i = 0; i < availablePos.length; i++) { const pos = availablePos[i]; // 在给定的位置下子，生成一个新的棋盘 const newBoard = this.generateNewBoard(pos, this.playerTurn); // 生成一个新的节点 const childState = new GameState(newBoard, changeTurn(this.playerTurn), this.depth + 1, this.alpha, this.beta); // 这里开始递归调用 getScore() 函数 const childScore = childState.getScore(); if (childScore > maxScore) { maxScore = childScore; maxIndex = i; // 这里保存产生了最大的分数的节点，之后会被用于进行下一步 this.choosenState = childState; this.alpha = maxScore; } if (this.alpha >= this.beta) { break; } } return maxScore;}// min 节点的处理与上面类似// ...

完整代码见alphabeta.js

总结

这样就简单地介绍了 minimax 算法和 alpha-beta 算法，并分别给出了一个简单的实现，然后在 tic-tac-toe 游戏中应用了算法。

文章中所提到的所有代码可见此项目：Tic-tac-toe-js。其中的 algorithms 文件夹中是两种算法的简单实现，src 文件中是游戏的代码。

文章开头说到了这篇文章起源于写2048游戏项目的过程中，之后我将 minimax 算法应用到了2048游戏的 AI 中，不过对于局面的评估函数尚不完善，现在 AI 只能勉强合成1024😢，还有很大的改进空间。

如果我的文章对你有帮助，欢迎打赏支持！

微信支付

支付宝

欢迎关注我的其它发布渠道

RSS # javascript # minimax # alpha-beta pruning # 游戏 # 算法 2017年总结 2018年总结

【本文地址】

公司简介

联系我们